home *** CD-ROM | disk | FTP | other *** search
/ Just Call Me Internet / Just Call Me Internet.iso / prog / atari / m2 / cat3src / cat / hashing2.i < prev    next >
Text File  |  1997-10-26  |  5KB  |  174 lines
  1. IMPLEMENTATION MODULE Hashing2;
  2.  
  3. FROM SYSTEM IMPORT ADDRESS;
  4. FROM Characters IMPORT CR, LF;
  5. FROM Storage IMPORT ALLOCATE, DEALLOCATE;
  6. (*IMPORT Storage;*)
  7. IMPORT MagicDOS;
  8. IMPORT MagicConvert;
  9. FROM Void IMPORT v;
  10.  
  11. CONST (*maxTab = 5003;*)
  12.       empty = 0FFFFH; (* leerer Listenplatz *)
  13.  
  14. TYPE maxCardArray = ARRAY[0..MAX(CARDINAL)] OF CARDINAL;
  15. TYPE maxCardPtr   = POINTER TO maxCardArray;
  16. TYPE hashHandle = POINTER TO hInfo;
  17. TYPE hInfo      = RECORD
  18.                     list   : maxCardPtr;
  19.                     entry  : CARDINAL;
  20.                     aAnz,
  21.                     actual : CARDINAL;
  22.                     hashMax: CARDINAL; (* entspricht maxTab! *)
  23.                     hash   : maxCardArray;
  24.                   END;
  25.  
  26. CONST maxPrim = 30;
  27. TYPE primArrayType = ARRAY[0..maxPrim] OF CARDINAL;
  28. CONST PRIM = primArrayType{2503, 3001, 3449, 4001, 4507, 5003,
  29.                            5501, 6007, 6521, 7001, 7507, 8009,
  30.                            9001,   10007,  11003,
  31.                            12007,  13001,  14009,
  32.                            15013,  16001,  18013,
  33.                            20011,  25013,  30011,
  34.                            35023,  40009,  45007,
  35.                            50021,  55001,  60013,
  36.                            65521};
  37.  
  38. PROCEDURE H(crc, maxTab : CARDINAL):CARDINAL;
  39. BEGIN
  40.   RETURN crc MOD maxTab
  41. END H;
  42.  
  43. PROCEDURE whatsGood():CARDINAL;
  44. (* Gibt die Primzahl zurck, die in diesem Fall genommen werden soll *)
  45. VAR isAvail : LONGCARD;
  46.     prim    : CARDINAL;
  47.     z       : CARDINAL;
  48. BEGIN
  49.   isAvail  := MagicDOS.Malloc(LONG(-1)); (* Wieviel ist da?              *)
  50.   prim := 0;
  51.   z := 0;
  52.   IF isAvail > MAX(CARDINAL) THEN isAvail := LONG(MAX(CARDINAL)) END;
  53.   WHILE (z <= maxPrim) & (SHORT(isAvail) >= PRIM[z])  DO
  54.     INC(z);
  55.   END;
  56.   IF z = 0 THEN
  57.     RETURN 0
  58.   ELSE
  59.     RETURN PRIM[z-1]
  60.   END;
  61. END whatsGood;
  62.  
  63. PROCEDURE ToHash(crcAdr : ADDRESS; anz, add : CARDINAL):hashHandle;
  64. (* gibt hashHandle zurck, die hashcrcs werden in einem Array[0..xx] *)
  65. (* bergeben, dessen Anzahl <anz> ist. <add> gibt die Anzahl der     *)
  66. (* noch zu erwartenden Nachrichten an                                *)
  67.  
  68. TYPE crcPtr = POINTER TO ARRAY[0..MAX(CARDINAL)] OF CARDINAL;
  69. VAR z    : CARDINAL;
  70.     crc  : crcPtr;
  71.  
  72.     zz   : CARDINAL;
  73.     ptr  : hashHandle;
  74.     prim : CARDINAL;
  75.  
  76. BEGIN
  77. (*  NEW(ptr); *)
  78.   prim := whatsGood();
  79.   IF prim = 0 THEN RETURN NIL END;
  80.   ptr := MagicDOS.Malloc(12+2*LONG(prim+1));
  81.   IF ptr = NIL THEN RETURN NIL END;
  82.   WITH ptr^ DO
  83.     hashMax := prim;
  84.     list := MagicDOS.Malloc(LONG(anz+add)*2);
  85.     IF (list # NIL) & (LONGCARD(list) # LONGCARD(0)) THEN
  86.       FOR z := 0 TO hashMax DO (* Hashtabelle l”schen *)
  87.         hash[z] := empty
  88.       END;
  89.       aAnz  := anz;
  90.       entry := 0;
  91.       crc   := crcAdr;
  92.       FOR z := 1 TO anz DO
  93.         AddCrc(ptr, crc^[z-1]);
  94.  
  95.       END;
  96.       RETURN ptr
  97.     ELSE
  98.       v.bool := MagicDOS.Mfree(ptr);
  99. (*      DISPOSE(ptr);*)
  100.     END;
  101.   END; (* WITH ptr^ DO *)
  102.   RETURN NIL
  103. END ToHash;
  104.  
  105. PROCEDURE ReleaseHash(ptr : hashHandle);
  106. BEGIN
  107. (*
  108.     Storage.DEALLOCATE(hash, LONG(hashMax+1)*2);
  109.     Storage.DEALLOCATE(list, LONG(last+1+additionalSpace)*2);
  110. *)
  111.   IF ptr # NIL THEN
  112.     v.bool := MagicDOS.Mfree(ptr^.list);
  113.     v.bool := MagicDOS.Mfree(ptr);
  114.   END;
  115. (*    DISPOSE(ptr);*)
  116. END ReleaseHash;
  117.  
  118. PROCEDURE FreeEntry(ptr : hashHandle; start : CARDINAL):CARDINAL;
  119. VAR next : CARDINAL;
  120. BEGIN
  121.   WHILE ptr^.list^[start] # empty DO start := ptr^.list^[start] END;
  122.   RETURN start;
  123. END FreeEntry;
  124.  
  125. PROCEDURE AddCrc(ptr : hashHandle; crc : CARDINAL);
  126. VAR nr : CARDINAL;
  127. BEGIN
  128.   IF ptr = NIL THEN RETURN END; (* Neu *)
  129.   WITH ptr^ DO
  130.     nr := H(crc, hashMax);
  131.     list^[entry] := empty;
  132.     IF hash[nr] = empty THEN
  133.       hash[nr] := entry;
  134.       (* Der Eintrag in der Liste ist <empty> *)
  135.     ELSE
  136.       (* Der Eintrag in der Hashtabelle ist dann schon fertig *)
  137.       list^[FreeEntry(ptr, hash[nr])] := entry
  138.     END;
  139.     INC(entry);
  140.   END;
  141. END AddCrc;
  142.  
  143. VAR actual : CARDINAL;
  144.  
  145. PROCEDURE GetFirst(ptr : hashHandle; crc : CARDINAL):CARDINAL; (* 0FFFFH nichts gefunden *)
  146. BEGIN
  147.   WITH ptr^ DO
  148.     actual := hash[H(crc, hashMax)];
  149.     RETURN actual
  150.   END;
  151. END GetFirst;
  152.  
  153. PROCEDURE GetNext(ptr : hashHandle):CARDINAL; (* 0FFFFH nicht gefunden *)
  154. BEGIN
  155.   WITH ptr^ DO
  156.     IF actual # empty THEN
  157.       actual := list^[actual]
  158.     END;
  159.     RETURN actual
  160.   END;
  161. END GetNext;
  162.  
  163. PROCEDURE getEmptyHash():hashHandle;
  164. BEGIN
  165.   RETURN NIL
  166. END getEmptyHash;
  167.  
  168. PROCEDURE emptyHash(h : hashHandle):BOOLEAN;
  169. BEGIN
  170.   RETURN h = NIL
  171. END emptyHash;
  172.  
  173. END Hashing2.
  174.